\section{Desarrollo}

\subsection{Preguntas del enunciado}

\begin{itemize}

\item Si queremos que las condiciones, (las cl'ausulas de los if y los while) sean booleanos solamente. C'omo podemos verificar esto est'aticamente? C'omo incide en la gram'atica? C'omo lo resuelven otros lenguajes de programaci'on?

La soluci'on que imlementamos fue decir que la condici'on de un if o un while tiene que ser de tipo \textit{boolean\_expression}, que se define como una formula booleana. De 'esta manera la verificaci'on se hace por sintaxis y no se llega al sistema de tipos.

Algunos lenguajes como $C$, toman cualquier valor distinto de $0$ como verdadero y $0$ como falso, de esta manera cualquier expresion puede castearse implicitamente a un valor booleano. Otros lenguajes usan un sistema de tipos ya que de 'esta manera pueden permitir expresiones mas complejas en las condiciones.


\lstset{
	breaklines=true
}

\begin{lstlisting}
if_statement { -> statement }
		= {if_then}			if [condition]:boolean_expression then [then_statements]:statement
							{ -> New statement.if_then(condition.boolean_expression, then_statements.statement) }
		| {if_then_else}	if [condition]:boolean_expression then [then_statements]:no_short_if_statement else [else_statements]:statement
							{ -> New statement.if_then_else(condition.boolean_expression, then_statements.statement, else_statements.statement) }
		;

	while_statement { -> statement }
		=					while [condition]:boolean_expression [body]:statement
							{ -> New statement.while(condition.boolean_expression, body.statement) }
		;

boolean_expression
		= {negation}				boolean_expression
		| {relational}				relational_expression
		| {or}						[left]:boolean_expression [right]:boolean_expression
		| {and}						[left]:boolean_expression [right]:boolean_expression
		;
\end{lstlisting}


\item Por qu'e no hacen falta terminadores de sentencia (ej .’;’) como en C/C++? Expliquen por
qu'e hacen falta en esos lenguajes y por qu'e no en nuestro caso? Justifiquen.


Los terminadores de sentencia como $;$ que se usa en C, son necesarios para poder distinguir donde empieza y donde termina una sentencia, debido a las particularidades de la sintaxis. En 'este ejemplo de c'odigo en C seria ambigua la siguiente expresi'on si no fuera por un terminador de sentencia:

\begin{verbatim}
int *a = 2 *a++
vs
int *a = 2; *a++;
\end{verbatim}

En el primer ejemplo el asterisco se toma como un producto, y en el segundo se entiende que $*a$ es una sentencia nueva y por lo tanto es una dereferenciaci'on del puntero $a$.

En nuestro caso no hace falta usar temrinadores de sentencias por la simplicidad de la sintaxis y por que no se producen 'estos casos ambiguos.


\item Si quisi'eramos que no importe el orden en que est'an definidas las funciones dentro del c'odigo, ¿C'omo lo har'iamos? ¿Y para soportar recursi'on?

La verificaci'on de referencias a funciones declaradas se implementa como una regla sem'antica. En nuestra implementaci'on cada vez que se encuentra una definici'on de funci'on, 'esta se guarda en una tabla y al encontrar una llamada a funci'on, se verifica si el nombre de la funci'on a ser llamada est'a en la tabla. 'Esto hace que sea necesario definir las funciones antes de ser usadas. Pero tambi'en permite implementar llamadas recursivas ya que la funci'on al ser llamada ya se va a encontrar en la tabla de definiciones.

Para hacer que no importe el orden de definici'on de funciones se puede realizar dos pasadas por el AST: una para mirar todas las definiciones de funciones y la otra para verificar las llamadas.

Tambi'en como una optimizaci'on, se puede armar la tabla de symbolos (funciones y/o variables globales si las hubiera) en el momento de construcci'on del AST.

\end{itemize}

\subsection{Soluci'on Propuesta}

\subsubsection{Gram'atica}

La gram'atica que se propone es una gram'atica LALR(1) ya que SableCC soporta la generaci'on de dicho tipo de parsers. Como SableCC genera un lexer junto con el parser, en las producciones se incluye informaci'on para el lexer. Se puede ver todo el c'odigo de la gram'atica en la secci'on \ref{sec:gramatica_apendice}

\subsubsection{SableCC}

SableCC\cite{sablecc} es un generador de parsers y lexer para Java. Basandose en la gram'atica especificada se genera un lexer basado en un aut'omata finito deterministico. Adem'as utilizando la misma gram'atica se genera un parser LALR(1).

\subsubsection{Ejecuci'on}

El proceso de ejecuci'on de un programa mylanga comienza con un lexer. El lexer tokeniza el c'odigo de entrada y luego el resultado se envia al parser. El parser al recibir los tokens procede a realizar el an'alisis sint'actico y a armar un AST. Tanto el lexer como el parser son generados por SableCC a partir de la definici'on de la gram'atica.

Una vez que se tiene el AST, significa que el an'alisis sint'actico fue exitoso y se procede a aplicar un an'alisis sem'antico. Se aplican las reglas que recorren el AST y verifican diferentes propiedades del c'odigo generado. Las reglas que se implementaron son:

\begin{itemize}
\item DuplicateFunctionRule: verifica que las funciones tengan una 'unica definici'on.
\item FunctionMustReturnRule: verifica que cada funci'on tenga una sentencia return al final del c'odigo.
\item UndefinedFunctionReferenceRule: verifica que todas las llamadas a funciones que se producen sean a funciones definidas dentro del programa.
\item UndefinedVariableReferenceRule: verifica que las variables usadas dentro de cada funci'on esten definidas previamente tomando en cuenta el scope de sus definiciones.
\end{itemize}

Al finalizar el an'alisis sem'antico y si 'este fue exitoso, se procede a interpretar el AST y generar los datos de salida. El proceso de ejecuci'on de un programa MyLanga se puede ver en 'este diagrama:

\begin{figure}[H]
        \centering
		\includegraphics[scale=0.50]{img/diagrama.png}
        %\subfloat[El proceso de ejecuci'on de un programa MyLanga]{\includegraphics[scale=0.50]{img/diagrama.png}}
        \caption{El proceso de ejecuci'on de un programa MyLanga}
\end{figure}

\subsubsection{Intérprete}

Un programa MyLanga se ejecuta mediante la utilización de un intérprete. El intérprete implementado funciona sobre la sintaxis abstracta del lenguaje.

El intérprete es básicamente una máquina de pila que realiza un recorrido del árbol de sintaxis abstracta del programa ejecutando diferentes operaciones de acuerdo al tipo de nodo en el que se encuentre.

Por ejemplo, en un nodo de la sintaxis abstracta que representa una constante numérica, el intérprete lee la constante asociada al nodo y guarda el valor en el tope de la pila. De manera similar, cuando el intérprete se encuentra en un nodo de la sintaxis abstracta que representa una operación binaria, el mismo desapila los dos operandos del tope de la pila, realiza la operación correspondiente con los mismos y luego deja el resultado de la operación en el tope de la pila. Además de almacenar los resultados temporarios de las operaciones, el intérprete utiliza una pila para realizar llamados a función y almacenar variables locales. Por este motivo, al encontrar una llamada a función el intérprete pone los parámetros de la llamada en la pila, guarda el estado actual, reserva lugar para las variables locales (este paso depende de la implementación empleada y se explica más adelante), y procede a ejecutar la función. Al utilizar una pila para realizar el pasaje de parámetros de la llamada a función, el intérprete soporta la ejecución de funciones recursivas.

El intérprete puede utilizar la misma pila tanto para almacenar resultados temporarios, parámetros de llamados a funciones y variables locales; o puede utilizar diferentes pilas para almacenar resultados temporarios, y parámetros de llamados a funcion/variables locales. La utilización de cualquiera de estas estratégias es igualmente funcional. Sin embargo, cada una tiene sus ventajas y desventajas.

Al utilizar pilas separadas para los resultados temporarios y los parámetros/variables locales, el intérprete se ve obligado a copiar los parámetros de la pila que almacena los resultados temporarios a la pila que almacena los parámetros de las llamadas a función antes de ejecutar la función. Así mismo, al utilizar pilas separadas el intérprete no necesita conocer la cantidad de variables locales que utiliza una función porque las mismas se van agregando a medida que son necesarias en el tope de la pila que contiene los parámetros/variables locales mientras se ejecuta la función.

Por el contrario, al utilizar la misma pila para almacenar resultados temporarios, realizar el pasaje de parámetros y almacenar las variables locales; el intérprete no se ve en la necesidad de copiar los parámetros de una pila a otra al momento de armar el frame de la llamada a función. Basta con que el intérprete evalúe los argumentos en el orden correcto y los mismos se encontrarán en la posición esperada dentro del frame. Sin embargo, la utilización de una única pila para almacenar todos los valores genera un problema al momento de almacenar las variables locales. El problema se debe a que el intérprete debe conocer la cantidad de variables locales que tiene una función para poder reservar espacio en la pila para los mismos.

Al realizar un llamado a función, el intérprete debe crear un frame para que se ejecute la función. El frame contiene como mínimo los parámetros para la función. Además, al crear el frame se guardan en la pila los valores de los ``registros'' de base y retorno. Se preserva el valore del registro base para poder utilizarlo para acceder a los parámetros y a las variables locales dentro de la ejecución de la función.

Los parámetros de la función se encuentran antes del registro de base en la pila, y las variables locales se deben almacenar también en la pila luego de que se han salvado los registros. Para que el esquema con una única pila funcione, se debe reservar lugar para almacenar todas las variables locales que utiliza la función antes de iniciar la ejecución de la misma debido a que se utiliza la misma pila para almacenar resultados temporarios.

Por ejemplo, dada la siguiente función en lenguaje MyLanga:

\begin{lstlisting}
function plusTwo(x) {
	z = x + 2
	return z
}
\end{lstlisting}

El estado de la pila en el intérprete luego de evaluar la expresión $x + 2$, pero antes de realizar la asignación a la variable local sería el siguiente:

\begin{figure}[H]
        \centering
		\includegraphics[scale=0.85]{img/stack.png}
        %\subfloat[La pila luego de evaluar $x + 2$]{\includegraphics[scale=0.85]{img/stack.png}}
        \caption{La pila luego de evaluar $x + 2$}
\end{figure}

En la figura se puede observar la estructura del frame que crea el intérprete y cómo de no reservarse de manera anticipada el almacenamiento para las variables locales, este esquema sería inviable debido a que se mezclarían los resultados intermedios de las operaciones con las variables locales.

La necesidad de conocer la cantidad de variables locales de manera anticipada genera un pequeño problema para el intérprete pues debe conocer la cantidad de variables locales que utiliza cada función antes de poder ejecutarla. En un lenguaje compilado, suele ser responsabilidad del compilador calcular el espacio requerido; y en lenguajes que se ejecutan sobre una máquina virtual también suele ser responsabilidad del compilador establecer la cantidad de variables locales que necesita un método para su ejecución, y luego poner a disposición de la máquina virtual esa cantidad. En nuestro caso, esto es inviable debido a que el programa se interpreta y no se compila. Sin embargo, esto no es un problema muy complicado de resolver. Antes de iniciar la ejecución de una función, el intérprete realiza la tarea que en el caso de un lenguaje compilado realiza el compilador y calcula la cantidad de variables locales que utiliza la función a ejecutar. Una vez conocido este valor, se reserva la cantidad de espacio requerida por las variables locales de la función.

Si bien el costo de calcular la cantidad de variables locales que posee una función no es muy grande, se decidió realizar una pequeña optimización. El intérprete adopta una política lazy al momento de calcular la cantidad de variables locales que utiliza una función. En lugar de calcularla de manera eager al momento de encontrar una definición de función, sólo calcula la cantidad de variables locales que utiliza una función al momento de invocarla. Además, el intérprete guarda la cantidad de variables locales que utiliza una función al ser invocada en caso que la misma función sea invocada nuevamente.
